package com.yubest;

/**
 * 给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
 *
 *
 *
 * 示例 1：[图片] img/0653.jpg
 *
 *
 * 输入: root = [5,3,6,2,4,null,7], k = 9
 * 输出: true
 * 示例 2：[图片] img/0653.jpg
 *
 *
 * 输入: root = [5,3,6,2,4,null,7], k = 28
 * 输出: false
 * 示例 3：
 *
 * 输入: root = [2,1,3], k = 4
 * 输出: true
 * 示例 4：
 *
 * 输入: root = [2,1,3], k = 1
 * 输出: false
 * 示例 5：
 *
 * 输入: root = [2,1,3], k = 3
 * 输出: true
 *  
 *
 * 提示:
 *
 * 二叉树的节点个数的范围是  [1, 10^4].
 * -10^4 <= Node.val <= 10^4
 * root 为二叉搜索树
 * -10^5 <= k <= 10^5
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author hweiyu
 * @Description
 * @Date 2021/11/11 14:33
 */
public class P0653 {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(2, new TreeNode(1), new TreeNode(3));
        new Solution653().findTarget(root, 4);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution653 {

    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root, k);
    }

    private boolean dfs(TreeNode node, TreeNode root, int sum) {
        if (null == node) {
            return false;
        }
        return isSame(root, sum, sum - node.val) || dfs(node.left, root, sum) || dfs(node.right, root, sum);
    }

    private boolean isSame(TreeNode node, int sum, int target) {
        if (null == node) {
            return false;
        }
        return node.val == target && sum != target * 2 || isSame(node.val > target ? node.left : node.right, sum, target);
    }
}
